元胞自动机揭示交通瘫痪成因：车多路窄惹的祸
导语
怎样缓解堵车？拓宽道路吧！
糟糕的交通不仅会耽误我们的出行时间，同时也会削弱一个城市的经济增长。
城市交通拥堵的传统研究方法都需要假定交通环境是稳定的，而这一点与真实情况并不相符。在真实世界中，城市的拥挤在空间上并不均匀，而且昼夜的车流量不等，白天的车流量很大。
一段从起点到终点的旅途中包含着大量的信息。出行目的和车辆尺寸，路况信息以及个人轨迹，这些都影响着我们如何去描述城市的交通拥堵。从起点到终点所包含的信息以什么样的方式影响着一个人的出行时间，以及又如何用这些信息去解释城市的交通拥堵？这是摆在研究者眼前的难题。
PNAS的一项研究认为：大量车辆驶入关键的主干道路是交通拥堵出现的主要原因，也是拥堵加剧、甚至交通瘫痪的根源所在。
论文原题：
Macroscopic dynamics and the collapse of urban traffic
论文地址：
https://www.pnas.org/content/115/50/12654
交通现状
随着现代的科技发展，手机和车载的GPS设备能够帮助我们获得更多的数据，我们能够通过这些“流动”的数据来描述城市交通的大致轮廓。
研究者测定了波士顿，旧金山和波哥大三座城市的通行时间。研究者发现个人的通行时间可能与路况信息和个人的出行目的相关。根据相关的数据，衡量了早高峰中一个小时的出行情况。发现在早高峰期间，车辆的数量呈现出对数正态分布，出门时间呈现出幂律分布（幂指数为负的幂函数）。
城市交通动态图
上图模拟了波士顿在早高峰时期的交通情况。从左到右依次代表着三种情况。
左侧的那幅图描述的是自由的流动的情况：交通车辆之间的影响非常的小，可以忽略不计。并且在路口呈现的排队等灯的情况也并没有相关性，是随机分布的。
在中间的那幅图中，交通的拥堵很明显呈现出了沿道路分布的情况，明显在空间当中是不均匀的。不过即便如此也保留了基本的道路通行能力。
在右侧的那幅图中，道路拥塞的情况已经连成了网络，使得交通基本上处于瘫痪的状态。
城市车辆分布图
如上图所示。研究者发现被跟踪调查的目标车辆的出行数量呈对数正态分布。而所有出行人员的分布则更加的宽泛。
旧金山湾区的交通拥堵恢复图示
交通拥堵是现代都市生活所带来的必然现象。在交通高峰时段过后，主干道路的交通情况会得到一定的恢复。研究者发现车辆数量的变化遵循指数衰减。研究者将重点研究交通恢复期，进一步了解城市中车辆的变化。
分析建模
元胞自动机
元胞自动机（Cellular Automata）是一种在空间和时间上都离散的演化动力系统。系统由基本几何形态的元胞（Cell）组成，这些元胞按照一定规则排列可以形成一个空间区域，然后每个元胞都具有若干种离散或者连续的潜在状态，这些状态在每一个时间步都会按照相同的规则发生变化，于是形成了整个元胞自动机的演化过程。人们通常通过元胞自动机来研究从局部简单的规则到整体复杂动态的涌现过程。
二维元胞自动机中的一种“滑翔机”模型
一维元胞自动机
一维元胞自动机，就是一种简单的元胞自动机（CA）模型。最简单的一维元胞自动机的状态集合为两个元素{0,1}。邻居是一个半径为1的区域，也就是每一个方格的左、右两个方格是它的邻居。如上图，黑色的方格是当前细胞，两边的白色方格是它的邻居。状态集只有{0，1}两个状态，也就是说方格只能有黑、白两种颜色。
NaSch模型
1992年，德国学者 Nagel 和 Schreckenberg 在第184号元胞自动机规则的基础上提出了一维交通流CA模型，即，NS 模型（或NaSch模型）。
184规则模拟交通流（1表示有车，0表示无车，并且每辆车只在其前面具有开放空间时（前面一个格子为 0）才向前移动。这里前方定义为格子的右向）。
在其演化的每个步骤中，184规则自动机同时对所有细胞使用以下规则生成下一个阵列中的每个细胞，以确定每个细胞的新状态：
NaSch 模型是一个交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新。
NS模型的规则如下：
加速过程。如果车辆的速度低于最大速度，且前方有空余的空间，那么在下一个时刻，速度会增加1。
减速过程。如果车辆发现前方在某一确定距离内有其他车辆，并且这个距离要小于它的速度，那么车辆的速度会减少。
随机因素。设定了其他随机因素，会导致车辆的速度减1，速度不低于零。
位置更新。车辆按照预定的方式前进。
NaSch 模型的演化图示
纵轴是时间轴，横轴是在某一时刻的路况情况。研究者发现，随着时间的推移，原本没有堵塞情况的路况会自动出现堵塞，并且拥堵情况会在道路上传递。
实验设计
在本篇论文中，研究者就使用了 NaSch 模型。
模拟环境图示
如上图所示，研究者依照城市的道路，使用了二维、最大速度为 3 的元胞自动机进行建模。
上方的小型插图表示。绿色的线路表示可以通行的线路，红色的线路表示无法通行的线路，而蓝色的线路表示改选过的线路。其中浅蓝色的车辆表示的是新加入网络的车辆。对于这张插图而言，因为有一辆浅蓝色的车辆新加入了网络，使得另外一辆车无法右拐，必须改选直行的线路。
运行模型时，研究者向系统中“加载”车辆。当一辆模拟的车辆载入道路网络以后，车辆行驶的路线是根据他们的目的地以及当前的路况信息所决定的。
根据研究者的设定，早晨 7 点半至 8 点半为早高峰（模拟实验中表示为 0 时刻至 1时刻）。因此研究者只在这个时间段内在网络中按照设定好的加载速度向道路网络中加载车辆。而后停止加载车辆，让系统能够有足够长的时间去恢复，这样研究者就可以在很长的时间内观察到交通拥堵的情况，以及交通恢复的情况。
道路网络中的车辆数量图像
依上图所示，研究者对五个城市的道路进行了建模模拟。每一个城市都从 0 时刻开始。按照相应的比例加载车辆，直到 1 时刻。而后，研究者进一步观察道路的恢复情况。他们发现从 1 时刻（t0）开始，道路的通行能力能够按照一定的负指数幂函数快速的恢复（车辆数量快速减少）。在这里，设定 t0 = 1，并设置为对数坐标，这样子我们就能够看到了图中的小图所表示的路况恢复的图像。
交通瘫痪的临界态分析
为了进一步更精准地刻画城市的交通状态，研究者把城市的交通分为了三种不同的状态，一是自由流动（Free flow），二是交通堵塞（Traffic jams），三是交通崩溃（Network collapse）。
如上图的 A 图 B 图的前半部分所示：在自由流动状态中，车辆之间并不会彼此影响。新加入的车辆，也不会影响其他车辆的通行时间。出行时间由行驶的距离决定。（其中星号表示每个城市当前的交通情况。）
但是当城市中车辆的数量超过一定阈值的时候。就会出现城市拥堵情况。根据上图中移除了初始值影响的图 C 所示，研究者发现城市的拥堵情况分布在了一条“交通拥堵带”（图C）上。如果在这样的时候，对交通出行的需求仍在持续的增加（对于模拟实验而言就是向道路网络中加入更多的车辆），研究者发现：不再能观测到车辆驶离交通网络，换句话说，几乎每一个人都堵在了道路上，几乎没有人能够到达目的地（离开道路网络）。此时，交通已经瘫痪。在图上就表现为数据点离开了交通拥堵带。
在先前的研究中已经发现，虽然城市会出现交通拥堵的，但是在大多数的时候都能够快速恢复，不会出现交通大瘫痪的情况。因此，接下来要研究汽车的数量是如何影响交通瘫痪的。
临界状态的区分。纵坐标轴表示的是道路中车辆的数量。横坐标轴表示的是时间。
研究者，在试验中找到了会发生交通大瘫痪的“临界车辆加载速度”（每个时刻向交通网络中加入一定数量的车辆）。在上图中，临界速度的恢复曲线被用彩色标示出来。通过图 A 以及调整过的图 B，研究者能清晰地发现超过临界状态以后，道路中车辆的数量就会出现无法减少的情况。而这一条线所代表的车辆加载速度就是交通崩溃的临界状态。而对应的黑色的切线则是服从幂律关系的临界指数。在这条切线上方的红色曲线就代表着交通出现大瘫痪需要多个小时才能够得以恢复的情形。
为什么会出现道路拥堵
就现实世界来说，出行花费和路线选择是影响出行时间的两大主要因素。主要原因有两点，费用能减少人们对私家车辆的使用；司机被鼓励去选择不拥堵、行程较短的路线。
不过，研究者的进一步探究表明：即便改变了出行道路选择算法等其他因素，“临界现象”都是稳定存在的。临界现象主要是由道路拥堵表现出来的“形状”决定的。研究者认为：大量车辆驶入关键的主干道路是交通拥堵出现的主要原因，也是拥堵扩大成交通瘫痪的根源所在。
如何避免交通瘫痪、缓解交通拥堵？增加主干道宽度，从而提高道路短时承载能力，会是一个有效的方法。
参考资料
元胞自动机：
https://zh.wikipedia.org/wiki/%E7%B4%B0%E8%83%9E%E8%87%AA%E5%8B%95%E6%A9%9F
第184号元胞自动机规则：
https://en.wikipedia.org/wiki/Rule_184
NaSch模型：
Nagel, K., & Schreckenberg, M. (1992). A cellular automaton model for freeway traffic Kai Nagel, Michael Schreckenberg. Journal de physique I, 2(12), 2221-2229.
作者：Leo
编辑：杨清怡
推荐阅读
推荐课程
PC端链接：
https://campus.swarma.org/gpac=10686
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！